import { ListNode } from "../数组/对链表进行插入排序";

/**
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 * 合并k个升序链表
 * 分治合并
 * @param lists 
 */
const mergeKLists = (lists: Array<ListNode | null>): ListNode | null => {
    const len = lists.length;
    // 编辑判断
    if (len === 0) return null
    if (len <= 1) return lists[0]

    /**
     * 合并两个有序的链表
     * @param l 
     * @param r 
     */
    const merge = (l: ListNode | null, r: ListNode | null) => {
        // 边界判断
        if (l === null) return r;
        if (r === null) return l

        let dHead = new ListNode(),
            h = dHead;
        while (l !== null && r !== null) {
            if (l.val < r.val) {
                // 左 < 右
                h = h.next = l;
                l = l.next;
            } else {
                // 左 >= 右
                h = h.next = r;
                r = r.next;
            }
        }
        // 左右可能有的不为空
        h.next = l === null ? r : l
        return dHead.next
    }
    // [0, 1, 2, 3]
    const d = (s = 0, e = len - 1): ListNode | null => {
        // 两者相等, 返回改元素即可
        if (s === e) return lists[s]
        // 两者相差一个元素了
        if (e - s === 1) return merge(lists[s], lists[e])
        const m = (s + e) >> 1;
        // 合并左边的
        const fi: ListNode | null = d(s, m)
        // 合并右边的
        const se: ListNode | null = d(m + 1, e)

        // 合并两边
        return merge(fi, se);
    }

    return d()
};


/**
 * 顺序合并
 */
const mergeKLists2 = (lists: Array<ListNode | null>): ListNode | null => {
    const len = lists.length;
    // 编辑判断
    if (len === 0) return null
    if (len <= 1) return lists[0]

    /**
     * 合并两个有序的链表
     * @param l 
     * @param r 
     */
    const merge = (l: ListNode | null, r: ListNode | null) => {
        // 边界判断
        if (l === null) return r;
        if (r === null) return l

        let dHead = new ListNode(),
            h = dHead;
        while (l !== null && r !== null) {
            if (l.val < r.val) {
                // 左 < 右
                h = h.next = l;
                l = l.next;
            } else {
                // 左 >= 右
                h = h.next = r;
                r = r.next;
            }
        }
        // 左右可能有的不为空
        h.next = l === null ? r : l
        return dHead.next
    }

    let head = lists[0];
    // 按逐个逐个排序
    for (let i = 1; i < len; i++) {
        head = merge(head, lists[i])
    }

    return head

};